package com.ting.test.algorithms.图;

import java.util.*;


public class 图的拓扑遍历 {
    public static void main(String[] args) {
        Graph graph = new Graph();
        topSort(graph);
    }

    private static List<Node> topSort(Graph graph) {
        if (graph == null) {
            return new ArrayList<>();
        }
        HashMap<Node, Integer> inmap = new HashMap();//表示每一个节点当前的入度
        Queue<Node> zeroQueue = new LinkedList<>();//表示当前入度为0的节点

        //第一次遍历，将入度为0的节点筛选出来，这些节点其实就是图的头结点
        for (Node node : graph.nodes.values()) {
            inmap.put(node, node.in);
            if (node.in == 0) {
                zeroQueue.add(node);
            }

        }

        List<Node> result = new ArrayList<>();
        while (!zeroQueue.isEmpty()) {
            Node poll = zeroQueue.poll();//取出一个入度为0的节点
            result.add(poll);
            //打印该节点
            for (Node node : poll.nexts) {//遍历该节点的所有相邻节点
                node.in -= 1;//移除相邻节点与该点的关系
                inmap.put(node, node.in);//移除后如果有节点的入度为0，则入队
                if (node.in == 0) {//
                    zeroQueue.add(node);
                }

            }

        }

        return result;

    }
}
